// Justin Cowen
// CSC 332 - Data Structures
// March 28, 2010
// Program #4
// This program uses the BinarySearchTree class and the various methods associated with it
// to read in a list of integers and output the result in a BST. As well as print the tree
// along with other methods such as height, leaf, and find. This program implementation 
// relies heavily on recursion within each of the height, leaf, and printTree methods.
//
// ****The testing of the Height method as well as the Leaf method is hardcoded in the 
//     main method of the program. In order to change what nodes the methods perform on
//     you must change the hardcode in the main method****

import java.io.*;

class Prog4<T extends Comparable <? super T>> extends BinarySearchTree <T>{

    public Prog4(){
        super ();
    }


    public void build(T[] arr){         // Build the BST from the array arr.
        BinarySearchTree BST = new BinarySearchTree();
        for(int i=0; i<arr.length; i++){
        BST.insert(arr[i]);
        }
    }
    
    private BinaryNode<T> find(T x){  //Return a reference to the node that 
        return find(x, root);         //contains the element x. Return null if x is 
    }	                              //not in the  BST. This is the driver. 
    
    private BinaryNode<T> find(T x, BinaryNode<T> n){  //recursive workhorse
    	
        if(n==null){           //element not found 
            return null;
        }
 
        int temp = x.compareTo(n.element);  //temp variable to store value of 
    	                                    //compareTo
        if(temp<0)
            return find(x, n.left);
        else if(temp>0)
            return find(x, n.right);
        else
            return n;   // Match
    }
    
    public int height(T x){   //return the height of the node that contains 
    	return height(find(x));  //the element x
    }
    
    private int height(BinaryNode<T> n){ //recursive workhorse
        if(n==null){   
            return -1;
        }
        else
            return Math.max(height(n.left),height(n.right))+1;
    }
    
    public int leaf(T x){                   //Print the element of each node					
        System.out.println("Leaves are: "); //that is a leaf. Return the number	
        return leaf(root);                  //of leaves. This is the driver.
    }
    
    private int leaf(BinaryNode<T> n){     //recursive workhorse
        if(n.left!=null&&n.right!=null){       //case 1 (left and right children)
        	return leaf(n.left)+leaf(n.right);
        }
        else if(n.left!=null&&n.right==null) //case 2(left child and no right children)
            return leaf(n.left);
        else if(n.right!=null&&n.left==null) //case 3(right child and no left children)
            return leaf(n.right);
        else if(n.left==null&&n.right==null){ //case 4(no children, print element 
            System.out.print(n.element+" ");  // and return 1
            return 1; 
        }
        else
        	return 0;
    }
    
    public void printTree(){                  //Override the printTree method 
        if( isEmpty( ) )                      //of the BinarySearchTree class. 
            System.out.println("Empty tree"); //This will be a modified inorder 
        else                                  //traversal. This is the driver.
            System.out.println("Root is: "+root.element); //print root
            printTree(root);
    }
    
    private void printTree(BinaryNode<T> n){ //recursive workhorse
          
        if(n.left!= null) {   //print leaves
            System.out.println("Left child of "+n.element+" is "+n.left.element);
            printTree(n.left); 
        }
        if(n.right!= null) {
            System.out.println("Right child of "+n.element+" is "+n.right.element);
            printTree(n.right);    	     
        }
    }
    
        // Test program
    public static void main( String [ ] args )
    {
       Prog4<Integer> t = new Prog4<Integer>( );

       BufferedReader keyboard = new BufferedReader(new InputStreamReader (System.in));
       String line = null; 
       System.out.println("Enter integers to insert into a BinarySearchTree.");
       System.out.println("You may enter one or more integers per line.");
       System.out.println("To end input type Ctrl-d at the beginning of a new line");
       try{ line = keyboard.readLine(); }catch(IOException e){}
       while (line != null){
           String[] token = line.split("\\s+");
           for (int i=0; i<token.length; i++){
               System.out.print(token[i] + " ");  // echo print
               t.insert(Integer.parseInt(token[i]));
           }
           System.out.println();
           try{ line = keyboard.readLine(); }catch(IOException e){}
       }
       
       System.out.println("\n\nTest of the printTree method:");
       t.printTree();											//printTree method
       System.out.println("\nTest of Height method:");
       System.out.println("Height of Node 10 = "+t.height(10)); //hardcoded heights
       System.out.println("Height of Node 20 = "+t.height(20));
       System.out.println("Height of Node 28 = "+t.height(28));
       System.out.println("Height of Node 14 = "+t.height(14));
       System.out.println("\nTest of the Leaf method on Root:");//hardcoded test of leaf
       int temp = t.leaf(t.root);
       System.out.println("\n\nTotal: "+temp); //print total number of leaves
       
    }
}

